import java.util.*;

public class Solution740 {

    public int deleteAndEarn(int[] nums) {
        int max=0;
        for (int num:nums) {
            max=Math.max(max,num);
        }
        int[] mark=new int[max+1];
        for (int num:nums) {
            mark[num]+=num;
        }
        int[] dp=new int[max+1];
        dp[0]=mark[0];
        dp[1]=Math.max(mark[0],mark[1]);
        for (int i = 2; i < dp.length; i++) {
            dp[i]=Math.max(dp[i-2]+mark[i],dp[i-1]);
        }
        return dp[max];
    }
}
